1. Field of the Invention
This invention relates to methods and circuits for transmitting and storing information that is two dimensionally related and in particular relates to transmitting and storing digital information using a quadtree code with embedded Walsh transform coefficients.
2. Description of Related Art
Many two dimensional data structures are used in digital systems. A common example is a pixel map. Pixel maps are commonly used in video displays and in printers to describe a image being generated. With a pixel map, the color or intensity of each pixel is indicated by a corresponding datum in the pixel map. Pixel maps have rows and columns of data corresponding to the rows and columns of pixels on a video display and can include thousands or millions of data. For example, a standard VGA video display is 640 pixels wide and 480 pixels high and contains 307,200 pixels. A pixel map representing a two color image which fills a VGA display contains at least 307,200 bits of data, one bit for each pixel. For 256 colors or shades or grey, eight bits of data are required per pixel, and the pixel map contains at least 307,200 bytes. Because of the large number of pixels in a video image, pixel maps can require long times to transmit and large amounts of memory to store.
Encoding techniques exist for efficiently transmitting or storing two dimensional data structures without using pixel maps. One such technique uses quadtrees to describe images. A quadtree is a collection of nodes organized in levels and connected by branches. Each node in a quadtree structure has four branches connecting the node to four higher level nodes unless the node is a leaf node. Leaf nodes have no branches to higher levels.
For a two color image, each leaf node in the quadtree has a value which describes the color a particular area in the image. The level 0 node represents a block containing the entire image and is 1 if the image contains a foreground color and 0 if the image only contains a background color. A level 0 quadtree accurately represents only single color images. Nodes in higher levels of a quadtree correspond to sub-blocks of blocks described in preceding levels, and typically, more levels provide a more accurate quadtree representation of the image.
FIG. 1A shows a two color image having a foreground color region 100. FIG. 1B shows a quadtree which describes an approximation of the image of FIG. 1A. FIG. 1C shows blocks corresponding to the nodes of the quadtree of FIG. 1B. Level 1 of the quadtree corresponds to a partition which divides the image into four blocks 110, 120, 130, and 140. Block 120 contains only the background color and has node value zero. Blocks 110, 130, and 140 have node value one indicating at least a portion of blocks 110, 130, and 140 contains the foreground color. In FIG. 1B, level 1 nodes are 1011 using the convention that the top left block is the left-most branch, the top right block is the second branch from the left, bottom left block is the third, and bottom right block is the furthest right. A level 1 quadtree description of FIG. 1A replaces block 120 with the background color and each of blocks 110, 130, and 140 with the foreground color.
For level 2, blocks 110, 130, and 140 are divided into three sets of four sub-blocks 111-114, 131-134, and 141-144. Block 120 is not further divided because the level 1 description of block 120 accurately represents the constant background color of block 120. At level 2, blocks 113, 114, 131, 132, and 141 contain the foreground color and have node value one. Blocks 111, 112, 133, 134, and 142-144 contain only the background color and have node value zero.
The quadtree of FIG. 1B is expanded to level 2 by adding four new nodes and four new branches to each non-zero node of level 1. The level 2 quadtree of FIG. 1B approximates the image by filing blocks 113, 114, 131, 132, and 141 with the foreground color and filing blocks 111, 112, 120, 133, 134, and 142-144 with the background color. The level 2 quadtree is more accurate than either level 0 or 1 because smaller blocks are represented.
Each block 113, 114, 131, 132, and 141 which contain the foreground color, is partitioned into four sub-blocks to generate level 3. Higher levels are determined by recursive partitioning of blocks which contain the foreground color until the smallest blocks contain a single pixel.
A quadtree code is generated from a quadtree by ordering node values from the quadtree according to a predefined format. One format orders node values as read from left to right and from the top down. For the quadtree of FIG. 1B, a quadtree code is 1.vertline.1011.vertline.001111001000. (The symbol .vertline. is shown to separate quadtree code into levels for the reader's convenience and is not part of the quadtree code.) Quadtree codes often require less memory to store than do pixel maps and can be transmitted faster than a pixel map.
One disadvantage of the described quadtree code is that each block is restricted to a single color. A method that permits an efficient description of variation in of data values over the area of each block would be desirable.